// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-12 11:22
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.DateTrain;

import com.DataStruct.Tree.TwoBinaryTree.Node;

import java.util.ArrayList;
import java.util.List;

public class Postorder {
    /**
     * N叉树的后续遍历
     */
    public List<Integer> postorder(Node root) {
        ArrayList<Integer> ans = new ArrayList<>();
        /*
            遍历N叉树的每一个子树，如果当前节点有孩子节点则先遍历孩子节点，最后遍历当前根节点
         */
        preSearch(root, ans);
        return ans;
    }

    /**
     * 遍历N茶树，并且确定后序遍历序列
     *
     * @param root 根节点
     * @param ans  结果
     */
    private void preSearch(Node root, ArrayList<Integer> ans) {
        if (root == null) {
            return;
        }
        while (!root.children.isEmpty()) {
            // 当前节点有孩子节点,依次遍历孩子节点
            preSearch(root.children.remove(0), ans);
        }
        ans.add(root.val);
    }
}
